package com.dbh.alg.datastructure;

/**、
 * 链表反转
 * @author 董帮辉
 * @date 2025/4/28
 **/
public class E01Leetcode206 {

    public static ListNode reverseListNode1(ListNode head) {
        ListNode n1 = null;
        ListNode p = head;
        while (p != null) {
            n1 = new ListNode(p.val, n1);
            p = p.next;
        }
        return n1;
    }

    public static ListNode reverseListNode2(ListNode head) {
        List list1 = new List(head);
        List list2 = new List(null);
        while (true) {
            ListNode first = list1.removeFirst();
            if (first == null) {
                break;
            }
            list2.addFirst(first);
        }
        return list2.head;
    }

    static class List {
        ListNode head;

        public List(ListNode head) {
            this.head = head;
        }

        public void addFirst(ListNode first) {
            first.next = head;
            head = first;
        }

        public ListNode removeFirst() {
            ListNode first = head;
            if (first != null) {
                head = first.next;
            }
            return first;
        }
    }

    public static ListNode reverseListNode5(ListNode o1) {
        ListNode n1 = null;
        while (o1 != null) {
            // 老二位置记录下俩
            ListNode o2 = o1.next;
            // 让原链表的下一个节点指向新链表
            o1.next = n1;
            // 头结点还原为n1，不然头就是o1了
            n1 = o1;
            // 原链表的头就是之前的老二
            o1 = o2;
        }
        return n1;
    }

    public static void main(String[] args) {
        ListNode o1 = ListNode.of(1,2,3,4,5);
        System.out.println(o1);
        ListNode n1 = reverseListNode5(o1);
        System.out.println(n1);
    }
}
